package cn.com.yang.datastruct.graph;

/**
 * 有向图拓扑实现，逆序，数组从尾巴往头放，最下生成树
 * TODO
 * @author yangyijin
 * @since 2024年2月7日-下午4:54:24
 */
public class GraphTuopo {
	//图的订单和边，边是二维矩阵或者邻接表
	private Vertex[] vertexs;
	private int[][] adjMatix;
	private int nVertex;//计数器，定点的个数
	private StackX tStackX;//深度优先搜索的栈
	private Queue tQueue;//实现广度优先搜索的队列
	private final int MAX_VERTEX=20;//最大的顶点个数
	//保存拓扑排序后的结果
	private char[] sortedArray;//
	
	public GraphTuopo() {
		vertexs = new Vertex[MAX_VERTEX];
		adjMatix = new int[MAX_VERTEX][MAX_VERTEX];
		for(int i=0;i<MAX_VERTEX;i++) {
			for(int j=0;j<MAX_VERTEX;j++) {
				adjMatix[i][j]=0;
			}
		}
		nVertex=0;
		tStackX = new StackX();
		tQueue = new Queue();
		sortedArray=new char[MAX_VERTEX];
	}
	
	//向顶点插入数据
	public void insert(char label) {
		vertexs[nVertex++]=new Vertex(label);
	}
	//有了顶点够，更新矩阵关系
	public void addEdge(int start,int end) {
		//注意这里要更新一个部分，原因现在有方向
		adjMatix[start][end]=1;
	}
	//打印指定顶点中的label
	public void displayVertex(int v) {
		System.out.print(vertexs[v].label);
	}  
	/**
	 * 实现拓扑排序
	 */
	public void tuopo() {
		//把顶点的个数临时保存
		int tmpNverts = nVertex;
		while(nVertex>0) {
			//找到没有下一步的邻接顶点，找到返回下标，没有返回-1
			int curr = noNextVertex();
			if(curr==-1) {//环形图没法拓扑排序A-B-C-A
				System.out.print("环形图不能进行拓扑排序");
				break;
			}
			//找到了
			sortedArray[nVertex-1]=vertexs[curr].label;
			//把放进数组中的节点，从图中删除
			delVertex(curr);
		}
		//输出排序结果
		System.out.print("tuopo排序结果");
		for(int i=0;i<tmpNverts;i++) {
			System.out.print(sortedArray[i]+"\t");
		}
	}
	//删除顶点
	private void delVertex(int del) {
		if(del!=nVertex-1) {//不再尾巴
			//删除，实际上是把所有元素往前移动一位
			for(int i=del;i<nVertex;i++) {
				vertexs[i]=vertexs[i+1];
			}
			//矩阵要跟着修改，row和col下标移动
			//删掉的行的下面的行上移
			for(int row=del;row<nVertex-1;row++) {
				moveRow(row,nVertex);
			}
			//删掉的列的后面的列左移
			for(int col=del;col<nVertex-1;col++) {
				moveCol(col,nVertex);
			}
		}
		nVertex--;
	}

	/**
	 * 移动列
	 * @param col
	 * @param nVertex2
	 */
	private void moveCol(int col, int len) {
		//行不动，下一列往上一列移动
		for(int row=0;row<len;row++) {
			adjMatix[row][col]=adjMatix[row][col+1];
		}
	}

	/**
	 * 移动行
	 * @param row
	 * @param nVertex2
	 */
	private void moveRow(int row, int len) {
		//列不动，下一行往上一行移动列
		for(int col=0;col<len;col++) {
			adjMatix[row][col]=adjMatix[row+1][col];
		}
	}

	//找到没有进一步的邻接顶点的顶点
	private int noNextVertex() {
		//循环矩阵，所有的行的所有列都是0则代表没有
		boolean isAim;//是否找到目标的标记
		for(int row=0;row<nVertex;row++) {
			isAim=true;//是要找的目标
			for(int col=0;col<nVertex;col++) {
				if(adjMatix[row][col]==1) {//证明这个顶点有邻接的顶点
					isAim=false;
					break;
				}
			}
			if(isAim) {//意味着 isAim=false;没有被执行，当前row对应的顶点就是目标顶点
				return row;
			}
		}
		return -1;
	}
}
